int hprime[nmax];
const int constpr = 31;
void createhprime(int n) // should always be called first
{
    hprime[0]=1;
    fori(i,1,n)
        hprime[i] = hprime[i-1] * constpr;
}
struct hashstr
{
    vi harr;
    string hstr;
    hashstr(const string &s)
    {
        hstr = s;
        harr.clear();
        harr.pb(s[0]);
        fori(i,1,sz(s)-1)
            harr.pb(harr[i-1] + s[i] * hprime[i]);
    }

    hashstr& operator =(hashstr a)
    {
        swap(harr,a.harr);
        swap(hstr,a.hstr);
        return *this;
    }

    bool operator == (const hashstr &a)
    {
        return (sz(harr) == sz(a.harr) && harr.back() == a.harr.back());
    }

    bool operator != (const hashstr &a)
    {
        return !(*this == a);
    }

    bool operator < (const hashstr &a)
    {
        int n = sz(hstr), m = sz(a.hstr);
        int left = 0, right = min(n,m)-1, lastpos = -1;
        while (left <= right)
        {
            int mid = (left + right) >> 1;
            if (harr[mid]== a.harr[mid]) left = mid + 1, lastpos = mid;
                else right = mid -1;
        }
        if (lastpos == m-1)
            return false;
        if (lastpos == n-1)
            return true;
        else
            return (hstr[lastpos+1] < a.hstr[lastpos+1]);
    }

    bool operator > (const hashstr &a)
    {
        return !((*this < a) || (*this == a));
    }

};

//hash all substrings of length k.
void hash_len_k (const string &s, int k, vi &harr)
{
    int n = sz(s);
    harr.resize(n-k+1,0);
    harr[n-k] = s[n-k];
    fori(i,n-k+1,n-1)
        harr[n-k] += s[i] * hprime[i-n+k];
    ford(i,n-k-1,0)
        harr[i] = (harr[i+1] - s[i+k] * hprime[k-1] + s[i]) * hprime[1];
}
